import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution210 {
    /**
     * 图的拓扑排序
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses == 0) return new int[0];
        int[] inDegrees = new int[numCourses];
        for (int[] p : prerequisites) {
            inDegrees[p[0]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegrees.length; i++) {
            if (inDegrees[i] == 0) queue.add(i);
        }
        int count = 0;
        int[] res = new int[numCourses];
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            res[count++] = cur;
            for (int[] p : prerequisites) {
                if (p[1] == cur) {
                    inDegrees[p[0]]--;
                    if (inDegrees[p[0]] == 0) queue.add(p[0]);
                }
            }
        }
        if (count == numCourses) return res;
        return new int[0];
    }
}
